Magnum One/Magnum One (Mid-American Digital) (Disc Manufacturing).iso/d3/spellf.arc/SPELLF.DOC

Text File | 1989-10-30 | 19KB | 404 lines

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
^                                                                   ^
^    DOCUMENTATION FOR                                              ^
^                                                                   ^
^    SPELLF   !Tiny Trainable Spellfilter  Ver. 1.01                ^
^                                                                   ^
^    (c) 1989 Kas & Rita Thomas. All rights reserved.               ^
^                                                                   ^
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

You may distribute SPELLF to your friends.   But if you do so,  please
register   your copy with us today,  by sending $10  (in cash,  check,
M.O.,  stamps,  whatever) to: Kas & Rita Thomas, 578  Fairfield  Ave.,
Stamford, CT 06902.

This  program  was created using Borland Turbo C (Ver.  2.0).  If  you
would like fully commented source code for SPELLF,  kindly send $25 in
lieu of the registration fee. In other words: For $25,  you get source
code AND registration, all in one shot (on disk).

When  you  write,  please tell us about your computer setup.  Are  you
using SPELLF on a laptop?  Which model? (Are you happy with it?)  We'd
be delighted to hear from you. Write to us today!





WHAT IS SPELLF? AND: WHAT ISN'T IT?

SPELLF is a spellfilter. We feel this word better describes the spirit
of this utility than the term "spellchecker,"  which implies a literal
brute-force comparison of words against a dictionary.  SPELLF does not
do this,  obviously. (The "dictionary"  file used by SPELLF is only 8K
in  size!)  Rather  than check literal spellings,  SPELLF  checks  the
"legality"  of substrings  within each word and reports out any  words
that  contain illegal letter combinations.  In this way,  SPELLF  acts
more  like a logical filter than a mere word-looker-upper.  You give a
text file to SPELLF, and the program acts as a sieve, reading the text
file  in and passing suspect words to "stdout"  (the  standard  output
device  for your computer;  usually the console).  The output is fully
redirectable,  which means you can have it show up on your printer (or
on disk) rather than on your screen.

SPELLF carries out its filtering at lightning speed: On the slowest 8-
MHz XT clone we could find, SPELLF took only 10  seconds to spellcheck
a  120K  text  file!  (It adds words to the  main  dictionary  at  the
blistering  rate  of 1,000   English words --  about 6 Kbytes  --  per
second.) On a 286 or 386 machine, you may see throughput rates five to
ten  times  higher.  Especially if you use redirection.  (The  biggest
runtime bottleneck for SPELLF is waiting for the screen to update.)

Speed  isn't SPELLF's primary virtue,  however.  Small size  (both  in
terms of disk image and RAM overhead)  is where SPELLF really  shines.
The program itself is just 12K,  making it perfect for use on  floppy-
disk-only  systems  (laptops,  for example)  and  systems  that  can't
accommodate the 200K spellcheckers that come with such programs as ...
well,  you  know  the big names.  At  runtime,  SPELLF  uses  approxi-
mately   76K  of  RAM (12K of core RAM and 64K of  "far  core"    heap
space).  For its dictionary,  SPELLF uses a disk file only 8 kilobytes
in size.  No matter how many words you stuff into this dictionary file
($.DIC), it never gets bigger than precisely 8K.

Another  virtue  of SPELLF is that it operates in  command-line  mode,
making it easy to invoke spellchecking from batch files.

And,  SPELLF's  output  (a list  of  suspect words,  with  their  line
locations in the original file) is redirectable. That is, you can make
the  suspect-word  list show up at your printer,  or in a new file  on
disk, rather than on the screen. (Again, this approach lends itself to
batch file applications.)





DISCLAIMERS

Whether or not you send us money,  no warranties are made with respect
to the program's performance, fitness, hardware compatibility, etc.

To run this program, you need at least 72K of free RAM and 20K of disk
space at all times. Any version of DOS should be fine.

Note: This program is designed to spellcheck standard ASCII text files
only.   Nothing disastrous will happen if you attempt to spellcheck  a
WordStar file.  SPELLF  merely   ignores   high-bit   characters.  For
this  reason,  control codes that  fall outside  the  normal  range of
alpha-numeric  ASCII  characters  pose  no problem whatsoever. But  if
your  word  processor  uses /b or /i for font  calls,  you   may   see
erroneous  exception-word  callouts  on  the  screen.

If  there is sufficient demand,  we will rewrite the program  to  take
care of format code detection. (Don't hold your breath, however!)





THE $.DIC FILE

Your  program  should have come bundled with an 8K file called  $.DIC.
SPELLF  looks  for this file at runtime;  it contains the  information
needed to conduct spellchecking (or spellfiltering)  operations.  This
file  MUST be present in the current working directory,  for SPELLF to
work properly.

The  $.DIC  dictionary  file that we created for  bundling  with  this
program contains data for 20,000  commonly used English words.  If you
did not get a copy of $.DIC,  don't panic:  SPELLF will let you create
your  own $.DIC file,  but you will have to supply your own core  word
list  (of  properly spelled words)  with  which to make the  file.  To
create a brand-new $.DIC file from scratch, do this:

1.  Be sure you are in a directory that contains no $.DIC file.  (If a
$.DIC file already exists, rename or delete it; otherwise the existing
file will be UPDATED to contain the new word list.)

2. Run SPELLF with two arguments as follows:


               SPELLF  {filename of word list} -a   [Enter]


Don't forget the "-a"  on the command line.  This tells SPELLF to  ADD
the contents of {filename} to $.DIC.

If $.DIC did not exist before,  a new file named $.DIC will show up in
your  current directory when you follow the above procedure.  You will
then be able to "spellcheck" any file against the $.DIC dictionary.

If a $.DIC file already existed in the current directory, the contents
(vocabulary) of {filename} will simply be ADDED to $.DIC. The previous
contents of $.DIC will be preserved. It is a true ADD operation.






CREATING CUSTOM DICTIONARIES

Obviously, you can use the foregoing procedure to create any number of
custom  dictionaries (scientific word lists,  lists of foreign  words,
computer terms, etc.) for use with the SPELLF program. All you need to
do  is supply the name of a file containing a list of scientific terms
(or whatever) on the command line:


                  SPELLF NEWWORDS.TXT -a  [Enter]


In  this case,  the vocabulary of NEWWORDS.TXT will be added to $.DIC.
(Once  again:  If $.DIC did not already  exist in the current  working
directory, it will be created. If it exists, it will be updated.)  The
filename  does not have to have a .TXT extension;  this is  merely  an
example.  Any extension is permissible. (Caution:  If you accidentally
supply the name of a spreadsheet or other non-text file,  you stand  a
chance  of corrupting your existing $.DIC file.  Always keep a  "good"
copy of $.DIC on a backup disk somewhere.)

Note  that SPELLF is not merely an  English-language spellchecker.  If
you  happen  to have a French word list on disk,  you can  use  it  to
create a French-language version of $.DIC, and hence a French-language
spellchecker. The copy of $.DIC that comes bundled with SPELLF happens
to  contain  20,000  English words.  It could just as  easily  contain
French, Spanish, German, or Italian words, etc.





SPELLCHECKING

To  spellcheck  a text file,  just type SPELLF at the DOS  prompt  and
supply the name of the text file you wish to examine.  Then hit Enter.
Example:


                    SPELLF {filename} [Enter]



If  you  type SPELLF DRAFT.DOC [Enter],  the file  DRAFT.DOC  will  be
rigorously spell-checked using the words contained in $.DIC. (Remember
that  SPELLF  expects the file $.DIC to be in the  same  directory  as
DRAFT.DOC.)  A complete list of suspect words and their line locations
will be printed to the screen. If you want,  the list of suspect words
can  show  up  in a separate disk file,  or be  printed  out  on  your
printer. This is called redirection.

To  redirect the output of SPELLF to a brand-new file called BADWORDS,
simply type:



                 SPELLF  DRAFT.DOC > BADWORDS [Enter]



During  program execution,  in this case,  nothing will happen on  the
screen (but the disk will be active). When the DOS prompt returns, you
should  see  that  there is a new  file,  BADWORDS,  in  your  current
directory. You can look at this file with the DOS command TYPE, or use
your favorite word processor to open it.

Note  that SPELLF operates much faster when redirection to a  file  is
used.  That's because the process of  displaying output on the  screen
(in  SPELLF's default mode)  is inherently slow --  slower,  at least,
than SPELLF's file I/O operations.

You may wish, occasionally, to redirect output to your printer. Again,
you can use DOS to do this:



                 SPELLF  DRAFT.DOC  > PRN  [Enter]


This  causes  the  file DRAFT.DOC to be spellchecked and  the  suspect
words to appear at the printer, rather than at the screen.






TESTING WORDS FOR PRESENCE IN THE DICTIONARY

You  can  test  words  for presence or absence in  the dictionary.
The procedure is very simple: Just type SPELLF and -t.  Like this:



                         SPELLF -t  [Enter]



As soon as the program loads,  a  query message comes up on the screen
asking  you to supply a word.  Just  type it on the screen;  then  hit
Enter.  SPELLF  will consult $.DIC to  see if the word  you  typed  is
already in the dictionary.  If it is, you'll be told so,  and you will
be  asked  if you want to test another word.  (Type 'y'  or  Enter  to
answer  in  the affirmative.)  If the word you typed was  NOT  in  the
dictionary,  you'll be told so,  and you will be given a chance to add
it.  No extra typing is required to add  the word:  Just hit Enter  OR
type 'y'  for yes.  (You must type 'n'  if you do NOT wish to add  the
word to $.DIC.)

You  may keep checking words in this fashion for as long as you  like.
The  loop  will stop when you answer 'n'  (No)  to the  "Test  another
word?" prompt.

"Test"  mode  thus  offers a  second  way  (besides  "Add"  mode;  see
"CREATING CUSTOM DICTIONARIES,"  above) to update the dictionary.  You
can update the $.DIC dictionary one word at a time simply by  entering
the test-word loop as above, quitting at any convenient point.

Obviously,  when you have more  than a handful of words to add to  the
dictionary,  it makes sense to create  a text file containing just the
words  in question,  and "feed"  it to SPELLF in "Add"  mode by typing
SPELLF <list name> -a , then Enter.





SPELLCHECKING VS. SPELLFILTERING

Conceptually,   there   are   two   ways  to  attack  the  problem  of
spellchecking:  You can approach it in a brute-force manner, comparing
every  word  in a file with entries in a dictionary . . . or  you  can
approach it as an "expert system" type of problem,  wherein an attempt
is  made  to catalog all known rules of spelling (and spellcheck on  a
logical basis rather than a lookup basis). The first approach -- brute
force lookup of words in an all-encompassing dictionary -- is familiar
to  anyone  who has ever used a fully  featured word  processor.  This
approach  is,  in theory,  infallible,   provided  the  dictionary  is
complete.  In the real world,  no dictionary  is ever large enough  to
approach completeness,  nor CAN a dictionary ever be foolproof, due to
the  changing  nature  of  the language.  Proper nouns  are  always  a
problem,  and new coinages are always entering  the language.  Indeed,
the  inherent "inventivity"  of English is one of its  most  endearing
characteristics. But this very  property  dooms  all  orthodox  spell-
checkers to failure.

The second approach -- that of examining the rules governing spelling,
and  constructing  a spellchecker based on those rules --  happens  to
coincide  with  the approach taken by most hyphenation programs.  Most
hyphenators  are state machines whose main operations consist of affix
analysis  and word-root parsing.  The same approach can be extended to
spellchecking.   Why not simply examine patterns of letters,  and  ask
whether  the  individual patterns are "legal constructs"  or  "illegal
constructs"  based  on  known  rules  of English spelling?  (Here,  by
patterns  we  mean  more  than  just   two-letter   combinations.)  An
adaptation of this approach is used in SPELLF.

The  state-machine  approach has many advantages over the  brute-force
method. For one thing, it requires no bulky dictionary (which, in many
conventional  programs,  consumes  200K  or more   of  disk  space  IN
COMPACTED FORM).  For another thing, it means that,  in theory anyway,
English  words  that  don't exist yet can  be  spellchecked  properly,
because  new  coinages will always (presumably)  follow the  rules  of
English-language  letter-combining.  (That is,  it's unlikely  anybody
will  coin words that contain unpronounceable combinations like "xbjt"
or  "tqtpp.")  A  rule-based program should be able to spellcheck  new
coinages  that it has not seen before.  This is a formidable advantage
over conventional spellchecking systems.

SPELLF  incorporates these ideas.  Plus,  it does so in ways that  are
simple, effective, and conducive to rapid program execution.

When we say that SPELLF is a spellfilter, we mean simply that the goal
of  the  program is to filter out illogical spellings and yield  up  a
list  of  words  whose letter-combinations don't make sense  from  the
standpoint of known rules of English spelling.





HOW THE PROGRAM WORKS (A TECHNICAL ASIDE, FOR PROGRAMMERS ONLY)

If  you're wondering how 20,000  or more English words can fit into an
8,192-byte  dictionary file,  consider that in 8,192  bytes there  are
65,536 bits, each of which can represent a unique hash code. The $.DIC
file that we've been discussing so far is not really a dictionary file
in the true sense of the word, but a hash table, each one-bit entry of
which represents a 16-bit hash code derived from a four-byte substring
of  whatever  word is currently being examined.  Words less than  five
letters  long  correspond to single entries in the  hash table;  words
with five or more letters are carried in the table as multiple hashes.
A five-letter word has two hash entries;  a  six-letter word has three
hash entries; etc.

During  runtime,  every  word in a  file is "factored  out"  into  its
constituent   hash   codes   (however   many   there  are),  and  each
corresponding hash position in the $.DIC file is checked.  If the hash
check  reveals  a  "legal"   combination of four  letters,  the  check
succeeds;  if the hash is illegal  (representing a letter  combination
not  found  in  the  table),  it fails and  the  word  is  flagged  as
"suspect."

A  16-letter word such as "incomprehensible"  contains 13  four-letter
substrings and has 13 corresponding hash codes,  each of which must be
checked against entries in the $.DIC table.  If even one check  fails,
the  word  is flagged as suspect,  and printed to "stdout."  The  word
"incomprehensible"  must pass  all 13  checks in order to be  presumed
correctly spelled.

Notice  that all checks are done in RAM;  the disk is not accessed  13
times when "incomprehensible"  is checked against $.DIC, because $.DIC
is captured to RAM at runtime.

The  concept of hashing spellcheckers is not new;  McIlroy created one
for the PDP-11  (IEEE Trans. Comm. COM-30, Jan. 1982, pp. 91-99),  and
another  attempt  at such a program is discussed in CRAFTING  TURBO  C
SOFTWARE COMPONENTS & UTILITIES by Richard S.  Wiener (1988,  Wiley  &
Sons).  What is new about SPELLF  is the small size of the hash  table,
and  the  concept  of  "spellfiltering"  as  opposed  to  conventional
spellchecking  from within a text document.  No one talks about  these
programs  as filters.  But that's essentially what they are.  You  run
SPELLF on a file in order to filter out bad words -- "suspect"  words.
The spelling is never actually "checked" in the literal sense.

One  can  argue  as to whether a 16-bit hash is adequate for  a  four-
letter substring.  We start from the assumption (which is demonstrably
true)  that five bits of information will suffice to encode 26 letters
of the alphabet. We also know that 16  letters can be mapped precisely
into  four bits.  Something slightly more than four bits is needed  to
unambiguously encode 26 letters, but the process of mapping 26 letters
into four bits isn't as dangerous as it sounds,  because:  (1)  the 16
most-frequently-used  letters of the alphabet are used with very  high
frequency  indeed,  and (2)  the remaining 10  letters can be assigned
hash  positions that tend to map over known-good portions of the  hash
table.  Accordingly,  in SPELLF,  the  ASCII  table is  renumbered  to
reflect  frequency  of  usage  and best-fit   mapping,  so  that  hash
collisions  are  seldom  "fatal"  in the sense  of  allowing  a  wrong
spelling to score as "right."

Still,  SPELLF is not perfect.  There are times when a misspelled word
is  counted as correct.  But this happens very infrequently.  (If  you
want to get a feel for this, run the program in "test" mode and try to
trick  the  dictionary  with various misspellings  of  common  words.)
Please  understand  that  we make no guarantee  of  SPELLF's  spelling
accuracy,  nor  do  we  contend that  it  is  untrickable.  SPELLF  is
imperfect -- like every spellchecker.

What SPELLF lacks in precision, however,  it more than makes up for in
speed,  ease  of  use,  and  compactness   (to   say  nothing  of  its
adaptability to batch file technique,  redirectable output, etc.), and
on balance,  we feel the "filter"  approach is every bit as useful  in
day-to-day  usage as the orthodox big-dictionary brute-force approach.
We'd love to know what YOU think;  write to us at 578  Fairfield Ave.,
Stamford,  CT 06902.  And enclose $25  for full Turbo C source  code,
ready to compile in the tiny model.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *